#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
namespace gyc {
	template<class T>
	class greater {
	public:
		bool operator()(const T& a, const T& b)
		{
			return a > b;
		}

	};

	template<class T>
	class greater<T*> {
	public:
		bool operator()(const T* const &a, const T* const &b)
		{
			return *a > *b;
		}

	};


	template<class T>
	class less{
	public:
		bool operator()(const T& a, const T& b)
		{
			return a < b;
		}

	};
	template<class T>
	class less<T*> {
	public:
		bool operator()(const T* const& a, const T* const& b)
		{
			return *a < *b;
		}


	};

	//默认是大堆
	template<class T, class container = vector<T>,class compare = greater<T>>
	class priority_queue {
	public:
		priority_queue()
		{}

		void push(const T& x)
		{
			_c.push_back(x);
		
			adjustup(_c.size() - 1);
		}

		void pop()
		{
				
			swap(_c[0], _c[_c.size() - 1]);
			_c.pop_back();

			adjustdown(0);

		}


		const T& top() const
		{
			return _c[0];
		}

		bool empty() const
		{
			return _c.empty();
		}

		size_t  size() const
		{
			return _c.size();
		}

	private:
		//向上
		void adjustup(size_t child)
		{
			compare com;
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com(_c[child] , _c[parent]))
				{
					swap(_c[child], _c[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else {
					break;
				}
			}
		}
		//向下
		void adjustdown(size_t parent)
		{
			compare com;
			size_t child = parent * 2 + 1;
			while (child < _c.size())
			{
				if (child + 1 <_c.size() && _c[child + 1] > _c[child])
				{
					child++;
				}
				if (com(_c[child], _c[parent]))
				{
					swap(_c[child], _c[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else {
					break;
				}
			}
		}


	private:
		container _c;

	};





}